/*
767. 重构字符串
给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:

输入: S = "aab"
输出: "aba"

示例 2:

输入: S = "aaab"
输出: ""

注意:

    S 只包含小写字母并且长度在[1, 500]区间内。
*/

class Solution
{
public:
    string reorganizeString(string S)
    {
        int count[26];
        if(S.size() <= 2) return S;
        for(ch a : S) {
            count[a - 'a']++;
        }
        int max = 0;
        for(int ct : count) {
            if(max < ct) {
                max = ct;
            }
        }
        if(max > (S.size() + 1) / 2) return "";
    }
};